
\section{Strategyproof Mechanisms for the 2-Facility Location Game: Outline}
\label{s:2facilities}

%We proceed to consider the case where the mechanism allocates 2 facilities. %
We proceed to discuss the key proof steps and the consequences of our main result:
%namely that any nice mechanism for 2-Facility Location, applied to instances with $n \geq 5$ agents, either admits a dictator, or always allocates the facilities to the two extreme locations of the instance. More formally, we show the following:

\begin{theorem}\label{thm:2fac-gen}
Let $F$ be any nice mechanism for the 2-Facility Location game with $n \geq 5$ agents. Then, either $F(\vec{x}) = ( \min \vec{x}, \max \vec{x} )$ for all instances $\vec{x}$, or there exists a unique dictator $j$ such that for all instances $\vec{x}$, $x_j \in F(\vec{x})$.
\end{theorem}

Notably, we are aware of only two nice mechanisms for 2-Facility Location with $n \geq 4$ agents, one for each case of Theorem~\ref{thm:2fac-gen}.
%
The {\sc Dictatorial} mechanism chooses a dictator $j$, and for each instance $\vec{x}$, allocates a facility to $x_j$. Then, it considers the distance of the dictator to the leftmost and the rightmost location, $d_l = |\min\vec{x} - x_j|$ and $d_r = |\max\vec{x} - x_j|$, respectively. The second facility is placed at $x_j - \max \{ d_l, 2 d_r \}$, if $d_l > d_r$, and to $x_j + \max \{ d_r, 2 d_l \}$, otherwise.
%
In fact, {\sc Dictatorial} is an adaptation of the mechanism of \cite{LSWZ10} for the circle. As in \cite[Section~5]{LSWZ10}, it can be shown that {\sc Dictatorial} is strategyproof and $(n-1)$-approximate for the line.
%
The {\sc Two-Extremes} mechanism places the facilities at $(\min\vec{x}, \max\vec{x})$, for all instances $\vec{x}$, and is group strategyproof, anonymous, and $(n-2)$-approximate \cite{PT09}.
%
By Theorem~\ref{thm:2fac-gen}, {\sc Two-Extremes} is the only anonymous nice mechanism for 2-Facility Location and its approximation ratio is best possible.

\begin{corollary}\label{cor:2fac-anonymous}
A deterministic anonymous mechanism $F$ for 2-Facility Location with $n \geq 5$ agents is strategyproof and has a bounded approximation ratio if and only if for all instances $\vec{x}$, $F(\vec{x}) = ( \min \vec{x}, \max \vec{x} )$.
\end{corollary}

\begin{corollary}\label{cor:2fac-approx}
Any deterministic strategyproof mechanism $F$ for 2-Facility Location with $n \geq 5$ agents has an approximation ratio of at least $n-2$.
\end{corollary}

\begin{proof}
For any set $N$ of $n \geq 5$ agents, we let $\vec{x} = (0\sep \{j\}, \eps\sep N\setminus\{j, k\}, 1\sep \{k\})$, where $j \in N$ is the dictator of $F$, if any, $k \in N \setminus \{j\}$, and $\eps \in (0, 1/n)$. By Theorem~\ref{thm:2fac-gen}, if $F$ has a bounded approximation ratio, then $F_1(\vec{x}) = 0$. For convenience, we let $F_2(\vec{x}) = a$.
%
By Proposition~\ref{prop:middle}, $a \geq \eps$. If $\eps \leq a < 2\eps$, $\cost[F(\vec{x})] \geq 1-\eps$. If $a \geq 2\eps$, $\cost[F(\vec{x})] \geq (n-2)\eps$. Since the optimal cost is $\eps$, the approximation of $F$ is at least $n-2$.
\qed\end{proof}


The crux, and the most technically involved part of the proof of Theorem~\ref{thm:2fac-gen} is to establish the characterization for instances with 3 agents. More specifically, in Section~\ref{s:3agents}, we show that any nice mechanism for 2-Facility Location with 3 agents either places the facilities at the two extremes, or admits a \emph{partial dictator}, namely an agent allocated a facility for all, but possibly one, of agent permutations.

\begin{theorem}\label{thm:3agents}
Let $F$ be any nice mechanism for 2-Facility Location with $n = 3$ agents. Then, there exist at most two permutations $\pi_1$, $\pi_2$ with $\pi_1(2) = \pi_2(2)$ such that for all instances $\vec{x}$ where the agents are arranged on the line according to $\pi_1$ or $\pi_2$, $\med \vec{x} \in F(\vec{x})$. For any other permutation $\pi$ and instance $\vec{x}$, where the agents are arranged on the line according to $\pi$, $F(\vec{x}) = ( \min \vec{x}, \max \vec{x} )$.
\end{theorem}

%In addition to extending the ideas of \cite{Moul80} to 2-Facility Location games, the proof of Theorem~\ref{thm:3agents} makes, at several places, a novel use of locality and of the structure of the image sets of nice mechanisms.
%
The notion of a partial dictator is essential. The {\sc Combined} mechanism for 3 agents chooses a permutation $(i, j, k)$ of the agents, and for each instance $\vec{x}$, places the facilities using {\sc Two-Extremes}, if $x_i < x_k$, and {\sc Dictatorial} with dictator $j$, otherwise. Thus, {\sc Combined} admits a partial dictator, and is strategyproof and 2-approximate.

The next main step in the proof of Theorem~\ref{thm:2fac-gen} is to extend Theorem~\ref{thm:3agents} to 3-location instances.
%, where $n \geq 5$ agents are partitioned into 3 coalitions, and the agents of each coalition occupy the same location.
To this end, we first use partial group strategyproofness, and extend Theorem~\ref{thm:3agents} to 3-location instances (Corollary~\ref{cor:3agents}).
%
The key step is to show that when applied to 3-location instances with $n \geq 5$ agents, nice mechanisms %behave in a bit more restricted way than nice mechanisms for 3 agents. In particular, a nice mechanism for 3-location instances with $n \geq 5$ agents
do not have the option of a partial dictator. %either they admit a dictator, or they place the facilities at the two extremes.
More formally, in Section~\ref{s:3locations}, we show the following:

\begin{theorem}\label{thm:3locations}
Let $N$ be a set of $n \geq 5$ agents, and let $F$ be any nice mechanism for 2-Facility Location applied to instances in $\Ithr(N)$. Then, either there exists a unique dictator $j \in N$ such that for all instances $\vec{x} \in \Ithr(N)$, $x_j \in F(\vec{x})$, or for all instances $\vec{x} \in \Ithr(N)$, $F(\vec{x}) = ( \min \vec{x}, \max \vec{x} )$.
\end{theorem}

Finally, in Section~\ref{s:2fac-gen}, we employ induction on the number of agents, and extend Theorem~\ref{thm:3locations} to general instances with $n \geq 5$ agents, thus concluding the proof of Theorem~\ref{thm:2fac-gen}.
%
In the next three sections, we present the main ideas and technical arguments employed in the proof of Theorem~\ref{thm:2fac-gen}. We usually omit any quantification of $F$, with the understanding that $F$ denotes a nice mechanism for the 2-Facility Location game applied to the relevant class of instances.


\endinput
